package class_0923dynamicprogram;


import java.util.Arrays;

/**
 * https://leetcode.cn/problems/fibonacci-number/description/
 */
public class Fibonacci {
    /* 0 1 1 2 3 5 8 13 21 ... */
    // 递归法暴力求解
    public int fib(int n) {
        if(n==0){
            return 0;
        }
        else if(n==1){
            return 1;
        }
        else{
            return fib(n-1)+fib(n-2);
        }
        // 递归树在展开计算时， 存在重复计算。 明明之前求过递归子树的局部值， 但是又很傻地再求一遍白白浪费时间。
        // 上述说明了斐波那契数列求解递归的问题， 无脑递归导致重复计算。
    }
    // 自下而上的动态规划方法。
    // 时间复杂度O（n) 由于只算了递归树的一条简单路径（自下从叶子节点出发往上算）
    // 空间复杂度O（n) 由于开了一个n+1大小的数组， 存储这条路径的斐波那契数的值。
    public int fib2(int n) {
        if(n==0){
            return 0;
        }
        else if(n==1){
            return 1;
        }
        else {
            // n>=2
            int[] dp = new int[n + 1];//[0,n]长度的表
            dp[0] = 0;
            dp[1] = 1;
            for(int i=2;i<=n;i++){
                dp[i] = dp[i-1]+dp[i-2];
            }
            return dp[n];
        }
    }
    // 自下而上的动态规划方法---优化空间
    // 因为dp[i] = dp[i-1]+dp[i-2] 就纯粹是三个动态的数在玩，
    // 没必要开n+1的数组空间， 只需要保证它们实时更新就可以了。
    // 空间复杂度降为O（1）
    public int fib3(int n) {
        if(n==0){
            return 0;
        }
        else if(n==1){
            return 1;
        }
        else {
            // n>=2
            int[] dp = new int[3];//[0,n]长度的表
            dp[0] = 0;
            dp[1] = 1;
            for(int i=2;i<=n;i++){
                dp[2] = dp[1]+dp[0];//计算数据
                dp[0] = dp[1];//实时更新往后挪
                dp[1] = dp[2];
            }
            return dp[2];//dp[1]此时也等于dp[2]
        }
    }
    // 动态规划----自顶向下求解
    public int fib4(int n) {

        int[] dp = new int[n+1]; //记录一个一维数组， 用来存储值
        Arrays.fill(dp,-1);//无效值 初始化dp数组。
        return process(n, dp);
    }
    private int process(int aim, int[] dp) {
        if(aim==0){
            return 0;
        }
        else if(aim==1){
            return 1;
        }
        if(dp[aim] != -1){
            return dp[aim];// 如果表中存储了值（不为有效值）， 就直接取值。
        }
        //第一次计算的值就写入表中
        dp[aim] = process(aim-1, dp) + process(aim-2, dp);
        return dp[aim];//返回值
    }

    /*人类的智慧，通项公式法 时间复杂度O(1), 也省空间 */
    // 实际应用中， 由于浮点数的精度有效， 有精度问题。 最好不要使用。
    // 有关通项公式推导可以看看这个博主的。
    public int fib6(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;

        double phi = (1 + Math.sqrt(5)) / 2; // 黄金比例
        double psi = (1 - Math.sqrt(5)) / 2; // 另一根

        return (int) Math.round((Math.pow(phi, n) - Math.pow(psi, n)) / Math.sqrt(5));
    }

    //任何动态规划都对应着重复求解子问题的递归。
    // 自顶向上: 保留递归的写法， 但是牺牲了空间避免了重复求解（牺牲空间换时间）
    // 自下而上： 递归改成了迭代写法，  而且它还可以省空间。
}
